1. Field
The subject matter disclosed and claimed in this specification generally relates to methods and apparatus for signal processing, data analysis, and scientific computing.
2. Description of the Art
The Annex incorporated as part of this specification is a copy of a Technical Report entitled “Fast Digital Curvelet Transforms” published on-line in or about July 2005 and modified in March 2006. The Annex will be referred to in the specification that follows for tables, proofs, and detailed mathematical explanations. The Annex forms an integral part of the specification as a whole.
The last two decades have seen tremendous activity in the development of new mathematical and computational tools based on multiscale ideas. Today, multiscale or multiresolution ideas permeate many fields of contemporary science and technology. In the information sciences and especially signal processing, the development of wavelets and related ideas led to convenient tools to navigate through large datasets, to transmit compressed data rapidly, to remove noise from signals and images, and to identify crucial transient features in such datasets. In the field of scientific computing, wavelets and related multiscale methods sometimes allow for the speeding up of fundamental scientific computations such as in the numerical evaluation of the solution of partial differential equations. See reference 2 (this and other references are listed below at the end of the description of the preferred embodiments). By now, multiscale thinking is associated with an impressive and ever increasing list of success stories.
Despite considerable success, intense research in the last few years has shown that classical multiresolution ideas are far from being universally effective. Indeed, just as it was recognized that Fourier methods were not good for all purposes and consequently new systems such as wavelets were introduced, alternatives to wavelet analysis have been sought. In signal processing for example, an incentive for seeking an alternative to wavelet analysis is the fact that interesting phenomena occur along curves or sheets, e.g., edges in a two-dimensional image.
While wavelets are certainly suitable for dealing with objects where the interesting phenomena, e.g., singularities, are associated with exceptional points, they are ill-suited for detecting, organizing, or providing a compact representation of intermediate dimensional structures. Given the significance of such intermediate dimensional phenomena, a vigorous research effort has developed to provide better adapted alternatives by combining ideas from geometry with ideas from traditional multiscale analysis. See references 17, 19, 4, 31, 14, and 16.
A special member of this emerging family of multiscale geometric transforms is the curvelet transform, see references 8, 12, and 10, which was developed by Emmanuel Candès and David Donoho and others in the last few years in an attempt to overcome inherent limitations of traditional multiscale representations such as wavelets. Conceptually, the curvelet transform is a multiscale pyramid with many directions and positions at each length scale, and needle-shaped elements at fine or small scales. This pyramid is nonstandard, however. Indeed, curvelets have useful geometric features that set them apart from wavelets and the like. For instance, curvelets obey a parabolic scaling relation which says that at scale 2−j, each element has an envelope which is aligned along a ‘ridge’ of length 2−j/2 and width 2−j.
Curvelets are interesting because they efficiently address very important problems where wavelet ideas are far from ideal. Three examples of such problems are:
1. Optimally sparse representation of objects with edges. Curvelets provide optimally sparse representations of objects or images which display curve-punctuated smoothness, that is, smoothness except for discontinuity along a general curve with bounded curvature. Such representations are nearly as sparse as if the object were not singular and, as it turns out, far sparser than the wavelet decomposition of the object.
This phenomenon has immediate applications in approximation theory and in statistical estimation. As shown in Section 1.2 of the Annex, the representation is optimal in the sense that no other representation can yield a smaller asymptotic error with the same number of terms. The implication in statistics is that one can recover such objects from noisy data by simple curvelet shrinkage and obtain a Mean Squared Error (MSE) order of magnitude better than what is achieved by more traditional methods. In fact, the recovery is provably asymptotically near-optimal. The statistical optimality of the curvelet shrinkage extends to other situations involving indirect measurements as in a large class of ill-posed inverse problems. See reference 9.
2. Optimally sparse representation of wave propagators. Curvelets may also be a very significant tool for the analysis and the computation of partial differential equations. For example, a remarkable property is that curvelets faithfully model the geometry of wave propagation. Indeed, the action of the wave-group on a curvelet is well approximated by simply translating the center of the curvelet along the Hamiltonian flows. A physical interpretation of this result is that curvelets may be viewed as coherent waveforms with enough frequency localization so that they behave like waves but at the same time, with enough spatial localization so that they simultaneously behave like particles. See references 5 and 36.
This can be rigorously quantified, as alluded to in Section 1.2 of the Annex, in which the curvelet matrix is explained to be sparse and well-organized. It is sparse in the sense that the matrix entries in an arbitrary row or column decay nearly exponentially fast (i.e., faster than any negative polynomial). And it is well-organized in the sense that the very few nonnegligible entries occur near a few shifted diagonals. Informally speaking, one can think of curvelets as near-eigen functions of the solution operator to a large class of hyperbolic differential equations.
On the one hand, the enhanced sparsity simplifies mathematical analysis and allows one to prove sharper inequalities. On the other hand, the enhanced sparsity of the solution operator in the curvelet domain allows the design of new numerical algorithms with far better asymptotic properties in terms of the number of computations required to achieve a given accuracy. See reference [00127] 6.
3. Optimal image reconstruction in severely ill-posed problems. Curvelets also have special microlocal features which make them especially adapted to certain reconstruction problems with missing data. For example, in many important medical applications, the goal is to reconstruct an object f(x1,x2) from noisy and incomplete tomographic data, i.e., a subset of line integrals of f corrupted by additive noise modeling uncertainty in the measurements. See reference 33. This is especially challenging when one has incomplete data or in other words, when one cannot observe projections along every possible line but only along a given subset of such lines.
Because of its relevance in biomedical imaging, this problem has been extensively studied (as may be seen in the vast literature on computed tomography). Yet, curvelets offer surprisingly new quantitative insights. See reference 11. For example, a beautiful application of the phase-space localization of the curvelet transform allows a very precise description of those features of the object of f which can be reconstructed accurately from such data and how well, and of those features which cannot be recovered.
Roughly speaking, as shown in Section 1.2 of the Annex, the data acquisition geometry separates the curvelet expansion of the object into two pieces in which the first part of the expansion can be recovered accurately while the second part cannot. What is interesting here is that one can provably reconstruct the “recoverable” part with an accuracy similar to that one would achieve even if one had complete data. A quantitative theory exists showing that for some statistical models that allow for discontinuities in the object to be recovered, there are simple algorithms based on the shrinkage of curvelet-biorthogonal decompositions, which achieve optimal statistical rates of convergence; that is, such that there are no other estimating procedures which, in an asymptotic sense, give fundamentally better MSEs. See reference 11.
To summarize, the curvelet transform is mathematically valid and it has a very promising potential in traditional (and perhaps less traditional) application areas for wavelet-like ideas such as image processing, data analysis, and scientific computing.
Curvelets were first introduced by Emmanuel Candès and David Donoho in reference 8 and have been around for a little over six years by now. Soon after their introduction, researchers developed numerical algorithms for their implementation (see references 37 and 18), and scientists have started to report on a series of practical successes (see, for example, references 39, 38, 27, 26, and 20. These implementations are based on the original construction, see reference 8, which uses a pre-processing step involving a special partitioning of phase-space followed by the ridgelet transform, see references 4 and 7, which is applied to blocks of data that are well localized in space and frequency.
In the last three or four years, however, curvelets have been redesigned in an effort to make them easier to use and understand. As a result, the new construction is considerably simpler and totally transparent. The new mathematical architecture suggests innovative algorithmic strategies, and provides the opportunity to improve upon earlier implementations.
To realize this potential though, and deploy this technology to a wide range of problems, fast and accurate discrete curvelet transforms operating on digital data are needed.